\documentclass[a4paper]{article} 

\usepackage{listings}
\lstset{tabsize=4, %
	frame=shadowbox, %把代码用带有阴影的框圈起来
	commentstyle=\color{red!50!green!50!blue!50},%浅灰色的注释
	rulesepcolor=\color{red!20!green!20!blue!20},%代码块边框为淡青色
	keywordstyle=\color{blue!90}\bfseries, %代码关键字的颜色为蓝色，粗体
	showstringspaces=false,%不显示代码字符串中间的空格标记
	stringstyle=\ttfamily, % 代码字符串的特殊格式
	keepspaces=true, %
	breakindent=22pt, %
	numbers=left,%左侧显示行号
	stepnumber=1,%
	numberstyle=\tiny, %行号字体用小号
	basicstyle=\footnotesize, %
	showspaces=false, %
	flexiblecolumns=true, %
	breaklines=true, %对过长的代码自动换行
	breakautoindent=true,%
	breakindent=4em, %
	%escapebegin=\begin{CJK*}{GBK}{hei},escapeend=\end{CJK*},
	aboveskip=1em, %代码块边框
	fontadjust,
	captionpos=t,
	framextopmargin=2pt,framexbottommargin=2pt,
	abovecaptionskip=-3pt,belowcaptionskip=3pt,
	xleftmargin=4em,xrightmargin=4em, % 设定listing左右的空白
	texcl=true,
	% 设定中文冲突，断行，列模式，数学环境输入，listing数字的样式
	extendedchars=false,columns=flexible,mathescape=true
	% numbersep=-1em
}
\usepackage{cite}
\usepackage{fancyhdr}
\usepackage{lipsum}
\usepackage{extarrows}
\usepackage{ctex}
\usepackage{amsfonts,amssymb} 
\usepackage{amsmath} 
\usepackage{cases}
\usepackage{geometry}
\usepackage{graphicx}
\usepackage{listings}
\usepackage{xcolor}
\usepackage{framed}
\usepackage{float}
\usepackage{ulem}
\usepackage{booktabs}
\usepackage{amsthm}
\usepackage{tikz}
\usepackage{pgfplots}
\usepackage[ruled,vlined]{algorithm2e}
\pgfplotsset{width=10cm,compat=1.9}
\geometry{a4paper,left=3cm,right=3cm,top=3cm,bottom=3cm}

\begin{document}
	\begin{center}
		{\heiti {\huge 项目作业报告}}
	\end{center}
	
	\begin{center}
		{\large 求数2101\ 叶陈昊\ 3210106359}
	\end{center}
	
	\section{问题：BinaryTree的设计}
	课本提供的代码中, 给出的头文件
	\texttt{BinarySearchTree.h} , \texttt{AvlTree.h},
	\texttt{ RedBlackTree.h}和 \texttt{SplayTree.h}
	分别实现了对应的功能. 由于是教学代码, 每一个头文件都是独立的. 
	现在, 请根据它们各自的用途, 整理它们的逻辑关系, 重构全部代码, 
	并用继承关系予以表达.
	
	\section{设计过程}
	\subsection{设计思路}
	
	不难注意到，BinarySearchTree是四种二叉树中相对基础的一种.
	我们以此为思考点，通过分析\texttt{BinarySearchTree.h}中的代码，
	观察BST的节点结构和所用成员函数，展开我们的继承关系.
	
	树的继承关系如下：
	
	\begin{center}
		\begin{tikzpicture}[  
			level distance=1.5cm,  
			level 1/.style={sibling distance=3.5cm},  
			level 2/.style={sibling distance=2cm}  
			]  
			
			\node {BinaryTree{\footnotesize (BinaryNode)}}  
			child { node[align=center] {BinarySearchTree
					\\{\footnotesize(BinaryNode)}}} 										  
			child { node[align=center] {AvlTree \\ {\footnotesize (AvlNode)}} }  
			child { node[align=center] {RedBlackTree 
					\\ {\footnotesize (RedBlackNode)}} }
			child { node[align=center] {SplayTree 
					\\ {\footnotesize (BinaryNode)}} };  
			
		\end{tikzpicture}
	\end{center}

	注意到BinarySearchTree和SplayTree中的节点均使用了
	结构体\texttt{BinaryNode}, 而剩下两种树的节点其实在本质上是对
	\texttt{BinaryNode}中的成员进行了扩充，因此可以用继承的关系对剩下两种节点予以表达.
	
	节点的继承关系如下：

	\begin{center}
		\begin{tikzpicture}[  
			level distance=1.5cm,  
			level 1/.style={sibling distance=3.5cm},  
			level 2/.style={sibling distance=2cm}  
			]  
			
			\node {BinaryNode}  
			child { node {AvlNode}	}	  
			child { node {RedBlackNode}	};
			
		\end{tikzpicture}
	\end{center}
	
	结合二叉查找树的代码\texttt{BinarySearchTree.h}，我们提供了如下纯虚函数：
	\begin{itemize}
		\item \texttt{virtual const Comparable \& findMin( ) const = 0;}
		\item \texttt{virtual const Comparable \& findMax( ) const = 0;}
		\item \texttt{virtual bool contains( const Comparable \& x ) const = 0;}
		\item \texttt{virtual bool isEmpty( ) const = 0;}
		\item \texttt{virtual void printTree( ostream \& out = cout ) const = 0;}
		\item \texttt{virtual void makeEmpty( ) = 0;}
		\item \texttt{virtual void insert( const Comparable \& x ) = 0;}
		\item \texttt{virtual void insert( Comparable \&\& x ) = 0;}
		\item \texttt{virtual void remove( const Comparable \& x ) = 0;}
	\end{itemize}
	并在四个子类中重写以上函数.
	
	\subsection{原代码改动}
	\subsubsection{成员函数改动}
	由于\texttt{BinarySearchTree.h}中的\texttt{printTree}函数传入了一个输出流
	参数，而剩下三个树对应的函数没有任何参数，因此对剩下三个树的\texttt{printTree}
	进行修改，并对应修改私有成员函数\texttt{printTree}中的有关输出的内容.
	
	在重写函数的过程中，对于AvlTree而言除\texttt{printTree}函数外没有任何问题，
	因为它的函数名、传参类型等均与BinarySearchTree一致.而对其他两种树而言，
	要改动的稍微多一些.
	
	在RedBlackTree中出现了一点问题，原代码没有提供函数
	\texttt{void insert( Comparable \&\& x )}.如何在继承类中重写它呢？
	我们仿照\texttt{RedBlackTree.h}中的
	\texttt{void insert( const Comparable \& x )}函数内容，自己写了一个对应右值
	的版本.可以参见\texttt{TestTree.cpp}的运行结果，以了解其中调用了自己写的
	右值版本的\texttt{insert}函数.
	
	在SplayTree中出现了一些问题，第一是它也没有提供右值版本的\texttt{insert}函数，
	这个的解决方法同上.第二是原代码的三个函数（\texttt{findMin,findMax,contains}）
	跟基类有所不同，我们举其中一个例子（\texttt{findMin}）来说明，并展示修改它的方法.
	
	\begin{lstlisting}[language=C++]  
		const Comparable & findMin( )
		{
			...			
			splay( ptr->element, root );
			...
		}  
	
		void splay( const Comparable & x, BinaryNode * & t )
		{
			...
			nullNode->element = x;   // Guarantee a match
			
			for( ; ; )
			if( x < t->element )
			{
				...
				rightTreeMin->left = t;
				rightTreeMin = t;
				t = t->left;
			}
			else if( t->element < x )
			{
				...
				leftTreeMax->right = t;
				leftTreeMax = t;
				t = t->right;
			}
			else
			break;
			
			leftTreeMax->right = t->left;
			rightTreeMin->left = t->right;
			t->left = header.right;
			t->right = header.left;
		}
	\end{lstlisting}

	以上为\texttt{SplayTree.h}中的部分代码.
	观察这段代码知，\texttt{findMin}函数会在执行过程中用到\texttt{splay}函数，
	而\texttt{splay}函数会改变树的结构，因此\texttt{findMin}在原代码中没有声明为
	常量成员函数.
	
	要想重写一个\texttt{findMin}函数，在形式上，我们只需要对原代码的\texttt{findMin}
	函数做一个重载，即写为：
	\begin{lstlisting}[language=C++]
		const Comparable & findMin( ) const override
		{
			return findMin( );
		}
	\end{lstlisting}

	这样可以极小化原代码的修改（尤其是\texttt{splay}函数），同时实现基类函数重写.
	
	\subsubsection{继承节点改动}
	前文提到四种树的节点间的联系.我们在基类中令\texttt{BinaryNode}为基础节点
	（注意这个成员变量在类\texttt{BinaryTree}中要声明为\texttt{protected}，以
	实现后续继承能够使用它），
	在继承类\texttt{BinarySearchTree}和\texttt{SplayTree}中沿用此节点（需要写
	\texttt{using BinaryNode = typename BinaryTree<Comparable>::BinaryNode;}
	来正常使用节点，当然剩下两种树也需要写这句话来实现继承
	）.但剩下两种树的节点与\texttt{BinaryNode}有本质不同，
	我们分别探讨它们的解决方法.
	
	第一为AvlTree.它相较于基础节点增添了\texttt{height}，是AvlTree的一个特性.
	同时节点不一样说明不能使用基础节点的构造函数了，而是需要自己重写一个构造函数.
	不过基类节点中的\texttt{element}是可以保留的，因为这个变量的类型不会随着节点的
	继承而改变.我们可以在构造函数的内部实现这个赋值功能.
	综合上述，我们得到如下代码来实现继承.
	\begin{lstlisting}[language=C++]
		/* 节点相较于 BinaryNode 有新增变化, 需做改动 */
		struct AvlNode : public BinaryNode  
		{  
			AvlNode *left;
			AvlNode *right;
			int     height;
			
			AvlNode( const Comparable & ele, AvlNode *lt, AvlNode *rt, int h = 0 )
			: left{ lt }, right{ rt }, height{ h }
			{
				this->element = ele;
			}
			
			AvlNode( Comparable && ele, AvlNode *lt, AvlNode *rt, int h = 0 )
			: left{ lt }, right{ rt }, height{ h }
			{
				this->element = move( ele );
			}
		};  
	\end{lstlisting}
	
	第二为RedBlackTree.它相较于基础节点增添了\texttt{color}，是红黑树的一个特性.
	其他要注意的细节同AvlTree.修改代码如下.
	\begin{lstlisting}[language=C++]
		enum { RED, BLACK };
		
		/* 节点相较于 BinaryNode 有新增变化, 需做改动 */
		struct RedBlackNode: public BinaryNode
		{
			RedBlackNode *left;
			RedBlackNode *right;
			int           color;
			
			RedBlackNode( const Comparable & theElement = Comparable{ },
			RedBlackNode *lt = nullptr, RedBlackNode *rt = nullptr,
			int c = BLACK )
			: left{ lt }, right{ rt }, color{ c }
			{
				this->element = theElement;
			}
			
			RedBlackNode( Comparable && theElement, RedBlackNode *lt = nullptr,
			RedBlackNode *rt = nullptr, int c = BLACK )
			: left{ lt }, right{ rt }, color{ c }
			{
				this->element = move( theElement );
			}
		};
	\end{lstlisting}
	
	\section{代码测试}
	通过整合测试文件\texttt{TestBinarySearchTree.cpp} , \texttt{TestAvlTree.cpp},
	\texttt{ TestRedBlackTree.cpp}和 \texttt{TestSplayTree.cpp}并加以修改，
	我们得到了对\texttt{BinaryTree.h}的测试代码，见\texttt{TestTree.cpp}.
	\begin{itemize}
		\item 加入了打印函数\texttt{void printTree(BinaryTree<Comparable> \&t)}
	（小小的一个多态），目的是在某个阈值范围（\texttt{NUMS}）内输出树内存储的所有值.
		\item 相较于原代码，加入了对\texttt{makeEmpty}函数和\texttt{isEmpty}的测试.
		\item 在红黑树和伸展树的测试代码下测试\texttt{insert(7)}，以测试自己写的
		右值版本的\texttt{insert}的正确性.参见运行结果以确定是否调用此函数.
	\end{itemize}
	
	
	
	
\end{document}